{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Power of Heroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumOfPower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #英雄的力量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 <strong>力量</strong>&nbsp;定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>i<sub>0</sub></code>&nbsp;，<code>i<sub>1</sub></code>&nbsp;，<span style=\"\">... </span><code><span style=\"\">i<sub>k</sub></span></code><span style=\"\">&nbsp;</span>表示这组英雄在数组中的下标。那么这组英雄的力量为&nbsp;<code><font face=\"monospace\">max(nums[</font>i<sub>0</sub><font face=\"monospace\">],nums[</font>i<sub>1</sub><font face=\"monospace\">] ... nums[</font><span style=\"font-size:10.8333px\">i<sub>k</sub></span><font face=\"monospace\">])<sup>2</sup> * min(nums[</font>i<sub>0</sub><font face=\"monospace\">],nums[</font>i<sub>1</sub><font face=\"monospace\">] ... nums[</font><span style=\"font-size:10.8333px\">i<sub>k</sub></span><font face=\"monospace\">])</font></code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回所有可能的 <strong>非空</strong> 英雄组的 <strong>力量</strong> 之和。由于答案可能非常大，请你将结果对&nbsp;<code>10<sup>9 </sup>+ 7</code>&nbsp;<strong>取余。</strong></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,4]\n",
    "<b>输出：</b>141\n",
    "<b>解释：</b>\n",
    "第 1&nbsp;组：[2] 的力量为 2<sup>2</sup>&nbsp;* 2 = 8 。\n",
    "第 2&nbsp;组：[1] 的力量为 1<sup>2</sup> * 1 = 1 。\n",
    "第 3&nbsp;组：[4] 的力量为 4<sup>2</sup> * 4 = 64 。\n",
    "第 4&nbsp;组：[2,1] 的力量为 2<sup>2</sup> * 1 = 4 。\n",
    "第 5 组：[2,4] 的力量为 4<sup>2</sup> * 2 = 32 。\n",
    "第 6&nbsp;组：[1,4] 的力量为 4<sup>2</sup> * 1 = 16 。\n",
    "第​ ​​​​​​7&nbsp;组：[2,1,4] 的力量为 4<sup>2</sup>​​​​​​​ * 1 = 16 。\n",
    "所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [power-of-heroes](https://leetcode.cn/problems/power-of-heroes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [power-of-heroes](https://leetcode.cn/problems/power-of-heroes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4]', '[1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        total = nums[0]**3\n",
    "        current = nums[0]\n",
    "        if n == 1:\n",
    "            return total%(10**9+7)\n",
    "        for i in range(1,n):\n",
    "            total += nums[i]**3 + nums[i]**2*(current)\n",
    "            current = 2*current+nums[i]\n",
    "        return total%(10**9+7)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def sumOfPower(self, nums: List[int]) -> int:\n",
    "#         nums.sort()\n",
    "#         min1=[num%1000000007 for num in nums]\n",
    "#         max2=[num*num%1000000007 for num in nums]\n",
    "#         min_max2=[[curMin*curMax2%1000000007 for curMax2 in max2] for curMin in min1]\n",
    "#         answer=0\n",
    "#         for curDistance in range(len(nums)):\n",
    "#             curDistanceSum=0\n",
    "#             for curMinIndex in range(len(nums)-curDistance):\n",
    "\n",
    "#                 # curDistanceSum=(curDistanceSum+min1[curMinIndex]*max2[curMinIndex+curDistance]%1000000007)%1000000007\n",
    "\n",
    "#                 curDistanceSum=(curDistanceSum+min_max2[curMinIndex][curMinIndex+curDistance])%1000000007\n",
    "#             if curDistance==0:\n",
    "#                 curDistanceWeight=1\n",
    "#             else:\n",
    "#                 curDistanceWeight=pow(2,curDistance-1,1000000007)\n",
    "#             curDistanceSum=(curDistanceSum*curDistanceWeight)%1000000007\n",
    "#             answer=(answer+curDistanceSum)%1000000007\n",
    "#         return answer\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        answer=0\n",
    "        minSum=0\n",
    "        for num in nums:\n",
    "            answer=(answer+(num+minSum)*num*num)%1000000007\n",
    "            minSum=(minSum*2+num)%1000000007\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        minSum,powerSum=0,0\n",
    "        nums.sort()\n",
    "        for i in range(l):\n",
    "            tmp=(minSum+nums[i])*nums[i]%(10**9+7)*nums[i]%(10**9+7)\n",
    "            powerSum=(powerSum+tmp)%(10**9+7)\n",
    "            minSum=(minSum*2+nums[i])%(10**9+7)\n",
    "        return powerSum%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def sumOfPower(self, nums: List[int]) -> int:\n",
    "#         nums.sort()\n",
    "#         min1=[num%1000000007 for num in nums]\n",
    "#         max2=[num*num%1000000007 for num in nums]\n",
    "#         min_max2=[[curMin*curMax2%1000000007 for curMax2 in max2] for curMin in min1]\n",
    "#         answer=0\n",
    "#         for curDistance in range(len(nums)):\n",
    "#             curDistanceSum=0\n",
    "#             for curMinIndex in range(len(nums)-curDistance):\n",
    "\n",
    "#                 # curDistanceSum=(curDistanceSum+min1[curMinIndex]*max2[curMinIndex+curDistance]%1000000007)%1000000007\n",
    "\n",
    "#                 curDistanceSum=(curDistanceSum+min_max2[curMinIndex][curMinIndex+curDistance])%1000000007\n",
    "#             if curDistance==0:\n",
    "#                 curDistanceWeight=1\n",
    "#             else:\n",
    "#                 curDistanceWeight=pow(2,curDistance-1,1000000007)\n",
    "#             curDistanceSum=(curDistanceSum*curDistanceWeight)%1000000007\n",
    "#             answer=(answer+curDistanceSum)%1000000007\n",
    "#         return answer\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        answer=0\n",
    "        minSum=0\n",
    "        for num in nums:\n",
    "            answer=(answer+pow(num,3)+minSum*num*num)\n",
    "            minSum=(minSum*2+num)%1000000007\n",
    "        return answer%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        Mod=10**9+7\n",
    "        nums.sort()\n",
    "        s=0\n",
    "        prev=-1\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            res+=(num**2*(num+s))%Mod\n",
    "            res%=Mod\n",
    "            s=2*s+num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        tot = 0\n",
    "\n",
    "        n = len(nums)\n",
    "        S = nums[0] % MOD\n",
    "        for ii in range(1, n):\n",
    "            tot += (nums[ii]**2) * S\n",
    "            tot %= MOD\n",
    "\n",
    "            S = S*2 + nums[ii]\n",
    "            S %= MOD\n",
    "\n",
    "        for v in nums:\n",
    "            tot += v*v*v\n",
    "            tot %= MOD\n",
    "\n",
    "        tot %= MOD\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        # print(nums)\n",
    "        n = len(nums)\n",
    "        cur,ans = nums[0],0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            x = nums[i]\n",
    "            temp = (x % M) * (x % M) * (cur % M) % M\n",
    "            p = ((x % M) * (x % M) * (x % M)) % M\n",
    "            ans = (ans % M + temp % M + p) % M\n",
    "\n",
    "            cur = 2 * cur + x\n",
    "\n",
    "\n",
    "        ans += ((nums[0] % M) * (nums[0] % M) * (nums[0] % M)) % M\n",
    "        return ans % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        mod=1000000007\n",
    "        n=len(nums)\n",
    "        count=nums[0]**3\n",
    "        dp=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp=2*dp+nums[i]-nums[i-1]\n",
    "            count+=(nums[i]**2*dp)\n",
    "        return count%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        nums.sort()\n",
    "        # res = 0\n",
    "        # for i in range(0,len(nums)):\n",
    "        #     res += nums[i]**3\n",
    "        #     for j in range(i+1,len(nums)):\n",
    "        #         res += nums[i] *nums[j]*nums[j]*(2**(j-i-1))\n",
    "        #     res = res %mod\n",
    "        # return res\n",
    "        res = nums[len(nums)-1]**3\n",
    "        cur = 0\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            cur = (cur*2 + nums[i+1]*nums[i+1])\n",
    "            res += nums[i] ** 3 + cur*nums[i]\n",
    "        return res%mod\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=2681 lang=python\n",
    "#\n",
    "# [2681] 英雄的力量\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def sumOfPower(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        MAX_VAL = 10**9 + 7\n",
    "        nums.sort()\n",
    "\n",
    "        ans = 0\n",
    "        min_val = 0\n",
    "        for i in range(len(nums)):\n",
    "            min_val = (min_val + nums[i]) % MAX_VAL\n",
    "            ans = ((nums[i] ** 2 * min_val)%MAX_VAL + ans)%MAX_VAL\n",
    "            min_val = (min_val * 2 - nums[i]) % MAX_VAL\n",
    "            print(min_val)\n",
    "        return ans\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        min_value_prefix_sum = [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            # 1 2 4 5\n",
    "            # 1\n",
    "            # 1 2\n",
    "            # 1 1 2 4\n",
    "            # 1 1 1 1 2 2 4 5\n",
    "            crt_min_value_sum = min_value_prefix_sum[-1] * 2 + (num - (0 if i == 0 else nums[i - 1]))\n",
    "            min_value_prefix_sum.append(crt_min_value_sum % MOD)\n",
    "        #print(min_value_prefix_sum)\n",
    "            \n",
    "        for i, num in enumerate(nums):\n",
    "            ans = (ans + pow(num, 2, MOD) * min_value_prefix_sum[i + 1] % MOD) % MOD\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        pre_sum, res, mod = [0 for _ in range(len(nums))], nums[0] ** 3, 10 ** 9 + 7\n",
    "\n",
    "        for index in range(len(nums)):\n",
    "            if index > 0:\n",
    "                pre_sum[index] = (2 * pre_sum[index - 1] + nums[index - 1]) % mod\n",
    "                dp = (nums[index] + pre_sum[index]) % mod\n",
    "                res += dp * (nums[index] ** 2)\n",
    "\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        MOD=10**9+7\n",
    "        res=0\n",
    "        \n",
    "        last,cur=0,0\n",
    "        r=[0]\n",
    "        for it in nums:\n",
    "            cur=(it)+last*2%MOD\n",
    "            r.append(cur)\n",
    "            last=cur\n",
    "        #print(r)\n",
    "        for idx,it_max in enumerate(nums):\n",
    "            res+=(it_max%MOD*it_max%MOD*it_max%MOD+it_max%MOD*it_max%MOD*r[idx]%MOD)%MOD\n",
    "        return res%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        mod = int(1e9+7)\n",
    "        n = len(nums)\n",
    "        s = [0]\n",
    "        def quickMod(a, n):\n",
    "\n",
    "            res = 1\n",
    "            while n:\n",
    "                if n & 1:\n",
    "                    res = res * a % mod\n",
    "                a = a * a % mod\n",
    "                n >>= 1\n",
    "            return res\n",
    "        mi2 = 1\n",
    "        for i in range(n):\n",
    "            s.append((s[-1]+nums[i]*nums[i]*mi2%mod)%mod)\n",
    "            mi2 = mi2 * 2 % mod\n",
    "        ans = 0\n",
    "        inv2 = quickMod(2, mod-2)\n",
    "        invmi2 = inv2\n",
    "        for i in range(n):\n",
    "            ans = (ans + nums[i]**3 + nums[i]*(s[-1]-s[i+1])*invmi2%mod)%mod\n",
    "            invmi2 = invmi2 * inv2 % mod\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        MOD=10**9+7\n",
    "        res=0\n",
    "        \n",
    "        last,cur=0,0\n",
    "        r=[0]\n",
    "        for it in nums:\n",
    "            cur=(it)+last*2%MOD\n",
    "            r.append(cur)\n",
    "            last=cur\n",
    "        #print(r)\n",
    "        for idx,it_max in enumerate(nums):\n",
    "            res+=(it_max*it_max*it_max+it_max*it_max*r[idx])%MOD\n",
    "        return res%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        nums2 = [x * x % mod for x in nums]\n",
    "        power_two = [1]\n",
    "        for i in range(1, n):\n",
    "            power_two.append((power_two[-1]*2) % mod)\n",
    "        ans = nums[-1] * nums2[-1]\n",
    "        S = 0\n",
    "        for i in range(1, n):\n",
    "            S = (S * 2 + nums2[-i]) % mod\n",
    "            temp = (S + nums2[-i-1]) * nums[-i-1] % mod\n",
    "            ans = (ans + temp) % mod\n",
    "        # for i in range(n):\n",
    "        #     temp = (power_two[i] + power_two[n-1-i] - 2)*nums[i] % mod\n",
    "        #     ans = (ans + temp) % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        pref = [0]\n",
    "        for i, n in enumerate(nums):\n",
    "            pref.append((pref[-1] * 2 + n) % mod)\n",
    "        res = sum(n ** 3 % mod for n in nums) % mod\n",
    "        for i, n in enumerate(nums):\n",
    "            res += n ** 2 * pref[i]\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        sm = list(accumulate(nums, initial=0))\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for i, c in enumerate(nums):\n",
    "            \n",
    "            ans += (c**2) * pre % MOD\n",
    "            \n",
    "            ans += (c**3) % MOD\n",
    "            pre *= 2\n",
    "            pre += c\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "\n",
    "        res = sum([x**3 for x in nums])\n",
    "        nums.sort()\n",
    "        tmp = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            tmp = tmp * 2 + nums[i - 1]\n",
    "            res = res + tmp * (nums[i]**2)\n",
    "            res = res % (10 ** 9 + 7)\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10**9+7\n",
    "\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i]+nums[i]\n",
    "        \n",
    "        res = 0\n",
    "        p = 0\n",
    "        cnt = 1\n",
    "        p += pre[n]\n",
    "        for j in range(n-2, -1, -1):\n",
    "            p += cnt*pre[j]\n",
    "            cnt *= 2\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            res += (1*nums[i]*nums[i]%self.mod)*(p%self.mod)\n",
    "            p -= nums[i]\n",
    "            if i-1 >= 0:\n",
    "                p += nums[i-1]\n",
    "            if res >= self.mod:\n",
    "                res %= self.mod\n",
    "            p //= 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        l = list(accumulate(nums))\n",
    "        temp = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            ans += num ** 3 + temp * num ** 2\n",
    "            temp = temp * 2 + num \n",
    "            ans %= MOD\n",
    "            temp %= MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        nums2 = [x * x % mod for x in nums]\n",
    "        power_two = [1]\n",
    "        for i in range(1, n):\n",
    "            power_two.append((power_two[-1]*2) % mod)\n",
    "        ans = nums[-1] * nums2[-1]\n",
    "        S = 0\n",
    "        for i in range(1, n):\n",
    "            S = (S * 2 + nums2[-i]) % mod\n",
    "            temp = (S + nums2[-i-1]) * nums[-i-1] % mod\n",
    "            ans = (ans + temp) % mod\n",
    "        # for i in range(n):\n",
    "        #     temp = (power_two[i] + power_two[n-1-i] - 2)*nums[i] % mod\n",
    "        #     ans = (ans + temp) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        dp_s = 0\n",
    "        \n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp_s = (nums[i] + pre_sum[i]) % mod\n",
    "            pre_sum[i + 1] = (pre_sum[i] + dp_s) % mod\n",
    "            res = (res + nums[i] * nums[i] * dp_s) % mod\n",
    "        print(dp_s)\n",
    "        print(pre_sum)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, a: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        a.sort()\n",
    "        n=len(a)\n",
    "        b=[1]*n\n",
    "        for i in reversed(range(n)):\n",
    "            b[i]=a[i]*pow(2,n-i-1,mod)%mod\n",
    "        print(b)\n",
    "        c=ans=0\n",
    "        for i in range(n):\n",
    "            ans+=pow(a[i],3,mod)\n",
    "            if i>0:\n",
    "                ans=(ans+c*pow(pow(2,n-i,mod),mod-2,mod)%mod*a[i]*a[i]%mod)%mod\n",
    "            c=(c+b[i])%mod\n",
    "            # print(i,c,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        l = list(accumulate(nums))\n",
    "        temp = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            ans += num ** 3 + temp * num ** 2\n",
    "            temp = temp * 2 + num \n",
    "            ans %= MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "f = [1, 1]\n",
    "for i in range(2, 100001):\n",
    "    f.append(2 * f[-1] % mod)\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        if len(set(nums)) == 1:\n",
    "            return ((pow(2, n, mod) - 1) * nums[0] ** 3) % mod\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        \n",
    "        \n",
    "        ns = [(i * i) % mod for i in nums]\n",
    "        \n",
    "        @lru_cache\n",
    "        def get_s(i, j, x):\n",
    "            return i * j * f[x] % mod\n",
    "\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            print(t, res)\n",
    "            if i == 0:\n",
    "                res += nums[i] ** 3\n",
    "            else:\n",
    "                res += t * nums[i] * nums[i] + nums[i] ** 3\n",
    "            t *= 2\n",
    "            t += nums[i]\n",
    "            t %= mod\n",
    "            \n",
    "        \n",
    "        # t = [0] * n\n",
    "        # for i in range(n):\n",
    "            \n",
    "        return res % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, nums = len(nums), sorted(nums)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = (s + nums[i]) % MOD\n",
    "            s += dp[i]\n",
    "        print(dp)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += nums[i] ** 2 * dp[i]\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        f = [0 for _ in range(len(nums)+1)]\n",
    "        mod=10**9+7\n",
    "        inv=500000004\n",
    "        def binpow(a, b, m):\n",
    "            a = a % m\n",
    "            res = 1\n",
    "            while b > 0:\n",
    "                if (b & 1):\n",
    "                    res = res * a % m\n",
    "                a = a * a % m\n",
    "                b >>= 1\n",
    "            return res\n",
    "        for i in range(1, n+1):\n",
    "            f[i] = (nums[i-1]*nums[i-1]*binpow(2,i,mod))%mod\n",
    "        print(f)\n",
    "        for i in range(1, n+1):\n",
    "            f[i] =(f[i]+ f[i-1])%mod\n",
    "        print(f)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            ans = (ans+nums[i-1]*nums[i-1]*nums[i-1])%mod\n",
    "            r = nums[i-1]*((f[n]-f[i]+mod)%mod)*binpow(inv,i+1,mod)%mod\n",
    "            print(r)\n",
    "            ans =(ans+ r)%mod\n",
    "        ans = (ans+ nums[n-1]*nums[n-1]*nums[n-1])%mod\n",
    "        return ans %mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[0]**3\n",
    "        dp = [0]*len(nums)\n",
    "        dp_sum = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        dp_sum[0] = nums[0]\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = (nums[i] + dp_sum[i-1])%(10**9+7)\n",
    "            dp_sum[i] = (dp_sum[i-1]+dp[i])%(10**9+7)\n",
    "            ans = (ans+nums[i]**2*dp[i])%(10**9+7)\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        dp=[0 for i in range(len(nums))]\n",
    "        pre=[0 for i in range(len(nums)+1)]\n",
    "        mod=10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i]=(nums[i]+pre[i])%mod\n",
    "            pre[i+1]=(dp[i]+pre[i])%mod\n",
    "            \n",
    "            ans=(ans+nums[i]**2*dp[i])%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:      \n",
    "        nums.sort()\n",
    "        dp = [0 for i in range(len(nums))]\n",
    "        pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i] = (nums[i] + pre_sum[i]) % mod\n",
    "            pre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod\n",
    "            res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dp = [0 for i in range(len(nums))]\n",
    "        pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i] = (nums[i] + pre_sum[i]) % mod\n",
    "            pre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod\n",
    "            res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dp=[0 for _ in range(len(nums))]\n",
    "        pre_sum=[0 for _ in range(len(nums)+1)]\n",
    "        res=0\n",
    "        mod=10**9+7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i]=(nums[i]+pre_sum[i])%mod\n",
    "            pre_sum[i+1]=(pre_sum[i]+dp[i])%mod\n",
    "            res=(res+nums[i]**2*dp[i])%mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dp = [0 for i in range(len(nums))]\n",
    "        pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i] = (nums[i] + pre_sum[i]) % mod\n",
    "            pre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod\n",
    "            res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        dp = [0 for i in range(len(nums))]\n",
    "        pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i] = (nums[i] + pre_sum[i]) % mod\n",
    "            pre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod\n",
    "            res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dp = [0 for i in range(len(nums))]\n",
    "        pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i] = (nums[i] + pre_sum[i]) % mod\n",
    "            pre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod\n",
    "            res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        return res\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/power-of-heroes/solutions/2359660/ying-xiong-de-li-liang-by-leetcode-solut-9k1g/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        modn = 10**9+7\n",
    "        @lru_cache(None)\n",
    "        def check(st):\n",
    "            if st == 0:\n",
    "                return 10**9+1,0 #min max \n",
    "            for i in range(n-1,-1,-1):\n",
    "                if (1<<i) & st:\n",
    "                    tmpmi,tmpmx = check( (1<<i) ^ st )\n",
    "                    return  min(tmpmi, nums[i]),max(tmpmx,nums[i])\n",
    "            \n",
    "        for j in range(1<<n):\n",
    "            mi,mx = check(j)\n",
    "            # print(mx,mi,j)\n",
    "            ans += mx**2 *mi \n",
    "            ans = ans % modn \n",
    "            # print(ans)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        # mi = [10**9]*n \n",
    "        # mx = [0] * n \n",
    "        # for i in range(n):\n",
    "        #     print(mi,mx)\n",
    "        #     for j in range(i+1):\n",
    "        #         if mi[j]>nums[i]:\n",
    "        #             mi[j] = nums[i]\n",
    "        #         if mx[j]<nums[i]:\n",
    "        #             mx[j] = nums[i]\n",
    "        #         ans += mx[j]**2 * mi[j]\n",
    "        #         ans = ans % modn \n",
    "        #         print(ans)\n",
    "        # print(mi,mx)\n",
    "        # return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        s = nums[0]**3\n",
    "        mod = 10**9 + 7\n",
    "        s_d = [nums[0]]\n",
    "        d = [nums[0]]\n",
    "        for i in range(1, l):\n",
    "            d.append((nums[i]+s_d[-1])%mod)\n",
    "            s_d.append((s_d[-1]+d[-1])%mod)\n",
    "            s += (nums[i]**2%mod) * d[-1] % mod\n",
    "        return s % mod\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        pre=[0]*(n+1)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            dp[i]=(nums[i]+pre[i])%MOD\n",
    "            pre[i+1]=pre[i]+dp[i]%MOD\n",
    "            ans=(ans+nums[i]*nums[i]*dp[i])%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        # 先排序！很重要！\n",
    "        nums.sort()\n",
    "        N=200000\n",
    "        # 两个DP数组！（有点技巧在里面）\n",
    "        dp=[0]*N\n",
    "        dp_min=[0]*N\n",
    "        \n",
    "\n",
    "        # 由nums[0]构成的子集只有一个，最小值之和就是它本身，力量值也可以直接计算出来\n",
    "        # dp_min和dp要进行初始化！！！\n",
    "        dp_min[0]=nums[0]\n",
    "        dp[0]=nums[0]**3%mod\n",
    "        \n",
    "        # 枚举数字：（i:1~n-1）\n",
    "        for i in range(1,len(nums)):\n",
    "\t\t\t# ①dp_min[i]的值由三部分组成\n",
    "\t\t\t# 1、所有不含i的所有选法的集合————dp_min[i-1]\n",
    "\t\t\t# 2、只含i的选法————nums[i]\n",
    "\t\t\t# 3、所有含i的选法的集合————仍然是dp_min[i-1]\n",
    "            dp_min[i] = (2 * dp_min[i-1] + nums[i])%mod\n",
    "            \n",
    "            # ②dp[i]分为三个子集：\n",
    "            # 1、不含i的子集的力量总和————dp[i-1]\n",
    "            # 2、只含i————nums[i]**3\n",
    "            # 3、含1~i的子集的力量总和\n",
    "            dp[i] = (dp[i-1] + nums[i]**3 + dp_min[i-1]*nums[i]**2)%mod\n",
    "        return dp[len(nums)-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        # 先排序！很重要！\n",
    "        nums.sort()\n",
    "        N=200000\n",
    "        # 两个DP数组！（有点技巧在里面）\n",
    "        dp=[0]*N\n",
    "        dp_min=[0]*N\n",
    "        \n",
    "\n",
    "        # 由nums[0]构成的子集只有一个，最小值之和就是它本身，力量值也可以直接计算出来\n",
    "        # dp_min和dp要进行初始化！！！\n",
    "        dp_min[0]=nums[0]\n",
    "        dp[0]=nums[0]**3%mod\n",
    "        \n",
    "        # 枚举数字：（i:1~n-1）\n",
    "        for i in range(1,len(nums)):\n",
    "\t\t\t# ①dp_min[i]的值由三部分组成\n",
    "\t\t\t# 1、所有不含i的所有选法的集合————dp_min[i-1]\n",
    "\t\t\t# 2、只含i的选法————nums[i]\n",
    "\t\t\t# 3、所有含i的选法的集合————仍然是dp_min[i-1]\n",
    "            dp_min[i] = (2 * dp_min[i-1] + nums[i])%mod\n",
    "            \n",
    "            # ②dp[i]分为三个子集：\n",
    "            # 1、不含i的子集的力量总和————dp[i-1]\n",
    "            # 2、只含i————nums[i]**3\n",
    "            # 3、含1~i的子集的力量总和\n",
    "            dp[i] = (dp[i-1] + nums[i]**3 + dp_min[i-1]*nums[i]**2)%mod\n",
    "        return dp[len(nums)-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = []\n",
    "        cumdp= [0]\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        MOD = 10 **9 + 7 \n",
    "        for num in nums:\n",
    "            dp.append((cumdp[-1] + num)%MOD)\n",
    "            cumdp.append((cumdp[-1] + dp[-1])%MOD)\n",
    "            ans = ( ans + num*num *(dp[-1]))%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import os,sys,math\n",
    "from typing import List,Tuple,Optional\n",
    "\n",
    "MOD = 1000000000 + 7\n",
    "\n",
    "def mpow(a, n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    r = mpow(a, n // 2)\n",
    "    r = r * r\n",
    "    if n % 2 == 1:\n",
    "        r = r * a\n",
    "    return r % MOD\n",
    "\n",
    "def inv(a):\n",
    "    return mpow(a, MOD - 2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        vs1, vs2 = [], []\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            a = nums[i]\n",
    "            s += a*a*a\n",
    "            s %= MOD\n",
    "            \n",
    "            v1 = (a * inv(mpow(2, i))) % MOD\n",
    "            v2 = (a * a * mpow(2, i)) % MOD\n",
    "            vs1.append(v1)\n",
    "            vs2.append(v2)\n",
    "            \n",
    "            if i > 0:\n",
    "                vs1[i] += vs1[i-1]\n",
    "                s += vs2[i] * vs1[i-1] * inv(2)\n",
    "                s %= MOD\n",
    "        return s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        md=10**9+7\n",
    "\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]*nums[0]*nums[0]%md\n",
    "        \n",
    "        \n",
    "        sum_n=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            sum_n[i]=(sum_n[i-1]+nums[i-1]+sum_n[i-1])%md\n",
    "        print(nums)\n",
    "        print(sum_n)\n",
    "        \n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=nums[0]*nums[0]*nums[0]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=(nums[i-1]*nums[i-1]*(sum_n[i]-sum_n[i-1]))%md\n",
    "        print(dp)\n",
    "        return sum(dp)%md\n",
    "        # nums.sort()\n",
    "        # dp = [0 for i in range(len(nums))]\n",
    "        # pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        # res, mod = 0, 10 ** 9 + 7\n",
    "        # for i in range(len(nums)):\n",
    "        #     dp[i] = (nums[i] + pre_sum[i]) % mod\n",
    "        #     pre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod\n",
    "        #     res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        # print(nums)\n",
    "        # print(pre_sum)\n",
    "        # print(dp)\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dp = [0 for i in range(len(nums))]\n",
    "        pre_sum = [0 for i in range(len(nums) + 1)]\n",
    "        res, mod = 0, 10 ** 9 + 7\n",
    "        for i in range(len(nums)):\n",
    "            dp[i] = (nums[i] + pre_sum[i]) % mod\n",
    "            pre_sum[i + 1] = (pre_sum[i] + dp[i]) % mod\n",
    "            res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        print(nums)\n",
    "        print(pre_sum)\n",
    "        print(dp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        dp = [0] * n\n",
    "        preSum = [0] * (n + 1)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = preSum[i] + nums[i] % mod\n",
    "            preSum[i + 1] = preSum[i] + dp[i] % mod\n",
    "            res = (res + nums[i] * nums[i] * dp[i]) % mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        res=0;stub=10**9+7\n",
    "        length=len(nums)\n",
    "        nums=sorted(nums)\n",
    "        dpmin=[0 for i in range(length+1)] #dpmin[i]保存的是以nums第i个数字结尾的所有序列的最小元素之和   \n",
    "        preSum=[0 for i in range(length+1)]# preSum(i)=sum(dpmin) from 0 to i-1\n",
    "        '''\n",
    "        于是有：\n",
    "        preSum(i+1)=preSum(i)+dpmin(i)\n",
    "        dpmin(i)=nums[i]+preSum(i)\n",
    "        '''\n",
    "        for i in range(0,length):\n",
    "            delta=nums[i]*nums[i]\n",
    "            dpmin[i]=(nums[i]+preSum[i])%stub\n",
    "            preSum[i+1]=preSum[i]+dpmin[i]%stub\n",
    "            delta=(delta*dpmin[i])%stub\n",
    "            res=(res+delta)%stub\n",
    "            pass\n",
    "             \n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5 + 1\n",
    "MOD = 10 ** 9 + 7\n",
    "inv = [1] * N\n",
    "pow2 = [1] * N \n",
    "\n",
    "for i in range(1, N):\n",
    "    pow2[i] = pow2[i-1] * 2 % MOD\n",
    "    inv[i] = pow(pow2[i], MOD - 2, MOD)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        # inv = [0] * n \n",
    "        # for i in range(n):\n",
    "        #     inv[i] = pow(pow(2, i, MOD), MOD-2, MOD)\n",
    "        s = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            s[i] = (s[i-1] + nums[i-1] * inv[i-1]) % MOD \n",
    "        \n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            v = 0\n",
    "            if i > 0: v = x * x * pow2[i-1] * s[i]\n",
    "            res = (res + x * x * x + v) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        p = [0] * (n + 1)\n",
    "        inv = [0] * (n + 1)\n",
    "        pre = [0] * (n + 1)\n",
    "        p[0] = inv[0] = 1\n",
    "        inv2 = pow(2, MOD-2, MOD)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = (pre[i] + nums[i] * nums[i] * p[i]) % MOD\n",
    "            p[i+1] = p[i] * 2 % MOD\n",
    "            inv[i+1] = inv[i] * inv2 % MOD\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            t = (pre[n] - pre[i+1]) * inv[i+1] * nums[i] % MOD\n",
    "            res = (res + t + nums[i] * nums[i] * nums[i]) % MOD\n",
    "        return res\n",
    "\n",
    "# 2^(j-i-1) * nums[j] * nums[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n, mod = len(nums), 1_000_000_007\n",
    "        nums.sort()\n",
    "        numSqure = [x**2 for x in nums]\n",
    "        ans = 0\n",
    "        add = lambda x,y: (x+y) % mod\n",
    "        def calc(l, r):\n",
    "            print(l,r)\n",
    "            nonlocal ans\n",
    "            if l == r:\n",
    "                ans = add(ans, nums[l]*numSqure[l])\n",
    "            else:\n",
    "                m = (l+r) >> 1\n",
    "                # calc left and right\n",
    "                calc(l, m)\n",
    "                calc(m+1, r)\n",
    "                # calc left-right\n",
    "                Y, t = 0, 1\n",
    "                for y in numSqure[m+1:r+1]:\n",
    "                    Y = add(Y, t*y)\n",
    "                    t <<= 1\n",
    "                t = 1\n",
    "                for i in range(m,l-1,-1):\n",
    "                    x = nums[i]\n",
    "                    ans = add(ans, x*t*Y)\n",
    "                    t <<= 1\n",
    "        calc(0,n-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, nums: List[int]) -> int:\n",
    "        n, mod = len(nums), 1_000_000_007\n",
    "        nums.sort()\n",
    "        numSqure = [x**2 for x in nums]\n",
    "        ans = 0\n",
    "        add = lambda x,y: (x+y) % mod\n",
    "        def calc(l, r):\n",
    "            print(l,r)\n",
    "            nonlocal ans\n",
    "            if l == r:\n",
    "                ans = add(ans, nums[l]*numSqure[l])\n",
    "            else:\n",
    "                m = (l+r) >> 1\n",
    "                # calc left and right\n",
    "                calc(l, m)\n",
    "                calc(m+1, r)\n",
    "                # calc left-right\n",
    "                X, Y = 0, 0\n",
    "                for x in nums[l:m+1]:\n",
    "                    X = add(2*X, x)\n",
    "                for y in numSqure[m+1:r+1][::-1]:\n",
    "                    Y = add(2*Y, y)\n",
    "                ans = add(ans, X*Y)\n",
    "        calc(0,n-1)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
